#ifndef STX_ALGORITHM_POP_HEAP_HPP
#define STX_ALGORITHM_POP_HEAP_HPP

#include <stx/algorithm/common.hpp>
#include <stx/algorithm/push_heap.hpp>

namespace stx {

template <class Compare, class RandomAccessIterator>
inline void
pop_heap_impl(
    RandomAccessIterator first,
    RandomAccessIterator last,
    Compare comp,
    typename std::iterator_traits<RandomAccessIterator>::difference_type len)
{
    if (len > 1) {
        swap(*first, *--last);
        push_heap_front<Compare>(first, last, comp, len-1);
    }
}

template <class RandomAccessIterator, class Compare>
inline void
pop_heap(RandomAccessIterator first, RandomAccessIterator last, Compare comp)
{
    typedef typename add_lvalue_reference<Compare>::type comp_ref;
    pop_heap_impl<comp_ref>(first, last, comp, last - first);
}

template <class RandomAccessIterator>
inline void
pop_heap(RandomAccessIterator first, RandomAccessIterator last)
{
    stx::pop_heap(
        first,
        last,
        stx::less<typename std::iterator_traits<RandomAccessIterator>::value_type>());
}

} // namespace stx

#endif // STX_ALGORITHM_POP_HEAP_HPP
